from functools import lru_cache


@lru_cache(maxsize=128)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)


def fib2(n):
    if n < 2:
        return n
    return fib2(n - 1) + fib2(n - 2)


if __name__ == '__main__':
    import time

    t1 = time.time()
    print(fib(30))
    t2 = time.time()
    print(f'spend time: {(t2 - t1)*1000}')
    print(fib2(30))
    t3 = time.time()
    print(f'spend time: {(t3 - t2)*1000}')
